package ljl.codetop300;

import java.util.Arrays;

/**
 * 0 1 2 3 4
 * 1 1 1
 * 1 1 1 1
 * 1 1
 * 1 1
 * 1 1
 * 输入：nums = [2,3,1,1,4]
 * 输出：true
 * 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
 * 示例 2：
 *
 * 0 1 2 3 4
 * 1 1 1 1
 * 1 1 1
 * 1 1
 * 1
 * 0
 * 输入：nums = [3,2,1,0,4]
 * 输出：false
 * 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
 *
 * 感觉上得用 dp，因为需要不停的枚举
 */
public class _55_can_jump {

  /**
   * 虽然过了，但是很慢，需要 318ms
   */
  static class test {

    public static void main(String[] args) {
      System.out.println(new test().canJump(new int[]{3,2,1,0,4}));
    }

    public boolean canJump(int[] nums) {
      int len = nums.length;
      boolean[] dp = new boolean[len];
      dp[0] = true;
      for (int i = 0; i < len; i++) {
        if (!dp[i]) continue;
        for (int j = i + 1; j <= i + nums[i] && j < len; j++) {
          dp[j] = true;
        }
      }
      return dp[len - 1];
    }
  }

  public class off {
    public boolean canJump(int[] nums) {
      int n = nums.length;
      int rightmost = 0;
      for (int i = 0; i < n; ++i) {
        if (i > rightmost) return false;
        rightmost = Math.max(rightmost, i + nums[i]);
        if (rightmost >= n - 1) {
          return true;
        }
      }
      return true;
    }
  }

  static class copy_off {
    public boolean canJump(int[] nums) {
      int l = nums.length;
      int k = 0;
      for (int i = 0; i < l; i++) {
        if (i > k) return false;
        k = Math.max(k, i + nums[i]);
        if (k >= l - 1) return true;
      }
      return true;
    }
  }
}
